﻿#ifndef __SS_DOUBLY_LIST_H__
#define __SS_DOUBLY_LIST_H__
#include "../ssBaseDefine.h"
//#include <cstddef>
#include <memory.h>

#define SS_LIST_OK					0
#define SS_LIST_FULL				1	//链表已满
#define SS_LIST_DEL_NULL			2	//不能删除空节点
#define SS_LIST_DEL_INVAILD			3	//不能删除无效节点
#define SS_LIST_DEL_VAILD_ZERO		4	//有效节点数等于0
#define SS_LIST_DEL_ERROR_ITERATOR	5	//不能删除非本对象的节点
#define SS_LIST_ALLOT_NULL			6	//分配节点异常


namespace StarSeeker
{

template<ulint MEMSIZE>
class ssDoublyList
{
public:
#pragma pack(1)
	struct Node_s
	{
		friend class ssDoublyList;
	public:
		Node_s* Previous() { return pPrevious; }
		Node_s* Next() { return pNext; }
		i8 IsUsed() const { return isUsed; }
		void* Data() { return pData; }
	private:
		Node_s*			pPrevious;	//指向上一个节点
		Node_s*			pNext;		//指向下一个节点
		//ulint			order;		//节点创建序号
		ssDoublyList*	pOnwer;		//所在容器
		i8				isUsed;		//表示有效节点,0free,1used,2new_used
		char*			pData;		//存储的对象
	};
#pragma pack()

	ssDoublyList(void)
	{
		m_nUsedCount = 0;
		m_pUsedHead = 0;
		m_pUsedTail = 0;
		m_nFreeCount = 0;
		m_pFreeHead = 0;
		m_pFreeTail = 0;
		m_memCount = 0;
		m_nodeSize = sizeof(Node_s);
	}
	ssDoublyList(const ssDoublyList &cc)
	{
		m_nUsedCount = 0;
		m_pUsedHead = 0;
		m_pUsedTail = 0;
		m_nFreeCount = 0;
		m_pFreeHead = 0;
		m_pFreeTail = 0;
		m_memCount = 0;
		m_nodeSize = sizeof(Node_s);
		CopyFrom(cc);
	}
	virtual ~ssDoublyList(void)
	{
		Clear();
	}
	void operator = (const ssDoublyList &cc)
	{
		CopyFrom(cc);
	}

	//从另一个容器复制
	void CopyFrom(const ssDoublyList &cc)
	{
		Empty();
		Node_s* otherNode = cc.Begin();
		while (otherNode)
		{
			void* pData = this->Allot();
			memcpy(pData, otherNode->Data(), MEMSIZE);
			otherNode = otherNode->pNext;
		}
	}
	//分配一个空闲的单元
	void * Allot()
	{
		return AllotNode()->Data();
	}
	Node_s* AllotNode()
	{
		Node_s * pNode = 0;
		if (m_nFreeCount>0)
		{
			//取出无效链表的第一个
			pNode = m_pFreeHead;
			if (m_nFreeCount==1)
			{
				m_pFreeHead = m_pFreeTail = 0;
				m_nFreeCount = 0;
			}
			else
			{
				m_pFreeHead = m_pFreeHead->pNext;
				m_pFreeHead->pPrevious = 0;
				--m_nFreeCount;
			}
		}
		else
		{
			//创建新节点
			pNode = CreateNode();
			++m_memCount;
		}
		if (!pNode)
		{
			throw SS_LIST_ALLOT_NULL;
		}
		//放入有效链表的最后
		pNode->pNext = 0;
		if (m_nUsedCount==0)
		{
			m_pUsedHead = m_pUsedTail = pNode;
			pNode->pPrevious = 0;
			m_nUsedCount = 1;
		}
		else
		{
			m_pUsedTail->pNext = pNode;
			pNode->pPrevious = m_pUsedTail;
			m_pUsedTail = pNode;
			++m_nUsedCount;
		}
		if (pNode->isUsed!=2)
		{
			pNode->isUsed = 1;
		}
		return pNode;
	}
	//移除一个数据单元,返回下一个节点
	Node_s* EraseNode(Node_s* pNode)
	{
		Node_s * ret = 0;
		if (!pNode)
		{
			throw SS_LIST_DEL_NULL;
		}
		if (pNode->isUsed == 0)
		{
			throw SS_LIST_DEL_INVAILD;
		}
		if (m_nUsedCount == 0)
		{
			throw SS_LIST_DEL_VAILD_ZERO;
		}
		if (pNode->pOnwer != this)
		{
			throw SS_LIST_DEL_ERROR_ITERATOR;
		}

		//从有效链表中卸下节点
		if (m_nUsedCount==1)
		{
			m_pUsedHead = m_pUsedTail = 0;
			m_nUsedCount = 0;
		}
		else
		{
			//如果是头节点
			if (pNode==m_pUsedHead)
			{
				m_pUsedHead = m_pUsedHead->pNext;
				m_pUsedHead->pPrevious = 0;
				ret = m_pUsedHead;
			}
			//如果是尾节点
			else if (pNode==m_pUsedTail)
			{
				m_pUsedTail = m_pUsedTail->pPrevious;
				m_pUsedTail->pNext = 0;
			}
			else
			{
				pNode->pPrevious->pNext = ret = pNode->pNext;
				pNode->pNext->pPrevious = pNode->pPrevious;
			}
			--m_nUsedCount;
		}
		//放入无效链表的最前
		pNode->pPrevious = 0;
		if (m_nFreeCount==0)
		{
			m_pFreeHead = m_pFreeTail = pNode;
			m_nFreeCount = 1;
			pNode->pNext = 0;
		}
		else
		{
			m_pFreeHead->pPrevious = pNode;
			pNode->pNext = m_pFreeHead;
			m_pFreeHead = pNode;
			++m_nFreeCount;
		}
		pNode->isUsed = 0;
		return ret;
	}
	//必须传入链表中的对象指针才能删除
	Node_s* Erase(void *pData)
	{
		Node_s* pNode = FindNode(pData);
		if (pNode)
		{
			return EraseNode(pNode);
		}
		return 0;
	}
	//清除所有节点
	void Empty()
	{
		if (m_nUsedCount>0)
		{
			//将有效节点变成无效
			Node_s * pNode = m_pUsedHead;
			while(pNode)
			{
				pNode->isUsed = 0;
				pNode = pNode->pNext;
			}
			//将无效链表挂到有效链表后面,合并两个链表
			if (m_nFreeCount>0)
			{
				m_pUsedTail->pNext = m_pFreeHead;
				m_pFreeHead->pPrevious = m_pUsedTail;
			}
			else
			{
				m_pFreeTail = m_pUsedTail;
			}
			m_nFreeCount += m_nUsedCount;
			m_pFreeHead = m_pUsedHead;
			m_nUsedCount = 0;
			m_pUsedHead = 0;
			m_pUsedTail = 0;
		}
	}
	//获取有效节点头
	Node_s* Begin()const {return m_pUsedHead;}
	//获取有效节点尾
	Node_s* End()const {return m_pUsedTail;}
	//获取有效节点数
	ulint UsedCount()const {return m_nUsedCount;}
	//获取无效节点数
	ulint FreeCount()const {return m_nFreeCount;}
	//获取节点总数
	ulint Total()const {return m_nUsedCount+m_nFreeCount;}
	//获取无效节点头
	Node_s* FreeBegin()const { return m_pFreeHead; }
	//获取无效节点尾
	Node_s* FreeEnd()const { return m_pFreeTail; }

	//是否是该链表的节点
	bool IsFrom(Node_s* pNode) const
	{
		if (pNode)
		{
			return pNode->pOnwer==this;
		}
		return false;
	}
	bool DataIsFrom(void* pData) const
	{
		Node_s* pNode = FindNode(pData);
		return pNode!=0;
	}
	//是否是有效节点
	bool IsUsed(Node_s* itr) const
	{
		if (itr)
		{
			return itr->isUsed>0;
		}
		return false;
	}
	//释放无效节点内存
	void ReleaseFreeNode()
	{
		if (m_nFreeCount>0)
		{
			Node_s * pNode = m_pFreeHead;
			Node_s * pCurrentNode = 0;
			do
			{
				pCurrentNode = pNode;
				pNode = pNode->pNext;
				::free(pCurrentNode);
			} while (pNode);
			m_nFreeCount = 0;
			m_pFreeHead	= 0;
			m_pFreeTail	= 0;
		}
	}
	//清除数据内存
	void Clear()
	{
		if (m_nUsedCount > 0)
		{
			Node_s * pNode = m_pUsedHead;
			Node_s * pCurrentNode = 0;
			do
			{
				pCurrentNode = pNode;
				pNode = pNode->pNext;
				::free(pCurrentNode);
			} while (pNode);
		}
		if (m_nFreeCount > 0)
		{
			Node_s * pNode = m_pFreeHead;
			Node_s * pCurrentNode = 0;
			do
			{
				pCurrentNode = pNode;
				pNode = pNode->pNext;
				::free(pCurrentNode);
			} while (pNode);
		}
		m_nUsedCount = 0;
		m_pUsedHead = 0;
		m_pUsedTail = 0;
		m_nFreeCount = 0;
		m_pFreeHead = 0;
		m_pFreeTail = 0;
	}
protected:
	//创建新节点
	Node_s* CreateNode()
	{
		Node_s* pNode = (Node_s*)::malloc(sizeof(Node_s) + MEMSIZE);
		if (pNode)
		{
			pNode->pPrevious = 0;
			pNode->pNext = 0;
			pNode->isUsed = 2;
			pNode->pOnwer = this;
			pNode->pData = (char*)pNode+sizeof(Node_s);
		}
		return pNode;
	}
	//获取节点地址
	Node_s* FindNode(void* pData) const
	{
		if (pData)
		{
			char* head = (char*)pData - MEMSIZE;
			Node_s* pNode = (Node_s*)head;
			if (pNode->pOnwer == this)
			{
				return pNode;
			}
		}
		return 0;
	}
private:
	ulint			m_nUsedCount;		//有效节点数
	Node_s		*	m_pUsedHead;		//有效链表头节点
	Node_s		*	m_pUsedTail;		//有效链表尾节点
	ulint			m_nFreeCount;		//无效节点数
	Node_s		*	m_pFreeHead;		//无效链表头节点
	Node_s		*	m_pFreeTail;		//无效链表尾节点
	ulint			m_memCount;			//实际new的个数
	ulint			m_nodeSize;			//节点的大小
};

}
#endif
